#include <iostream>
#include <vector>

using namespace std;

// 912. 排序数组
// https://leetcode.cn/problems/sort-an-array/description/

class Solution
{
public:
    void merge(vector<int> &nums, int left, int mid, int right)
    {
        vector<int> temp(right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right)
        {
            if (nums[i] < nums[j])
            {
                temp[k++] = nums[i++];
            }
            else
            {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid)
        {
            temp[k++] = nums[i++];
        }
        while (j <= right)
        {
            temp[k++] = nums[j++];
        }

        for (int p = 0; p < temp.size(); p++)
        {
            nums[p + left] = temp[p];
        }
    }
    void mergeSort(vector<int> &nums, int left, int right)
    {
        if (left >= right)
            return;
        int mid = ((right - left) >> 1) + left;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    vector<int> sortArray(vector<int> &nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main()
{
    return 0;
}